|
In graph theory, a Moore graph is a regular graph of degree ''d'' and diameter ''k'' whose number of vertices equals the upper bound : An equivalent definition of a Moore graph is that it is a graph of diameter ''k'' with girth 2''k'' + 1. Another equivalent definition of a Moore graph ''G'' is that it has girth ''g = 2k+1'' and precisely cycles of length ''g,'' where ''n,m'' is the number of vertices (resp. edges) of ''G.'' They are in fact extremal with respect to the number of cycles whose length is the girth of the graph . Moore graphs were named by after Edward F. Moore, who posed the question of describing and classifying these graphs. As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage . The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth as well as odd girth, and again these graphs are cages. == Bounding vertices by degree and diameter == Let ''G'' be any graph with maximum degree ''d'' and diameter ''k'', and consider the tree formed by breadth first search starting from any vertex ''v''. This tree has 1 vertex at level 0 (''v'' itself), and at most ''d'' vertices at level 1 (the neighbors of ''v''). In the next level, there are at most ''d''(''d''-1) vertices: each neighbor of ''v'' uses one of its adjacencies to connect to ''v'' and so can have at most ''d''-1 neighbors at level 2. In general, a similar argument shows that at any level 1 ≤ ''i'' ≤ ''k'', there can be at most ''d''(''d''-1)''i'' vertices. Thus, the total number of vertices can be at most : originally defined a Moore graph as a graph for which this bound on the number of vertices is met exactly. Therefore, any Moore graph has the maximum number of vertices possible among all graphs with maximum degree ''d'' and diameter ''k''. Later, showed that Moore graphs can equivalently be defined as having diameter ''k'' and girth 2''k''+1; these two requirements combine to force the graph to be ''d''-regular for some ''d'' and to satisfy the vertex-counting formula. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Moore graph」の詳細全文を読む スポンサード リンク
|